#include <iostream>
#include <stack>

#include "common/utils.hpp"

void traversal(TreeNode* node, int targetSum, std::vector<int>& path, std::vector<std::vector<int>>& ret) {
    path.push_back(node->val);
    
    if (node->left == nullptr && node->right == nullptr) {
        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path[i];
        }

        if (sum == targetSum) ret.push_back(path);
    }

    if (node->left != nullptr) {
        traversal(node->left, targetSum, path, ret);
        path.pop_back(); // 回溯
    }
    
    if (node->right != nullptr) {
        traversal(node->right, targetSum, path, ret);
        path.pop_back(); // 回溯
    }
}

std::vector<std::vector<int>> pathSum(TreeNode* root, int targetSum) {
    std::vector<std::vector<int>> ret;
    if (root == nullptr) return ret;

    std::vector<int> path;
    traversal(root, targetSum, path, ret);

    return ret;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<std::vector<int>> ret = pathSum(commonRoot, 40);
    std::cout << "res: \n";
    for (int i = 0; i < ret.size(); i++) {
        printVector(ret[i]);
    }
}